package lc_307_区域和检索_数组可修改.线段树;

public class NumArray {

	class BinaryIndexedTree {
		int ceil;
		int[] bits;
		int[] nums;

		public BinaryIndexedTree(int ceil) {
			this.ceil = ceil + 10;
			this.bits = new int[this.ceil];
			this.nums = new int[ceil];
		}

		public void initArray(int[] nums) {
			for (int i = 0; i < nums.length; i++) {
				this.add(i, nums[i]);
			}
			this.nums = nums;
		}

		public int lowbit(int index) {
			return index & -index;
		}

		public void add(int index, int value) {
			this.nums[index] += value;
			index++;
			while (index < this.ceil) {
				this.bits[index] += value;
				index += this.lowbit(index);
			}
		}

		public int query(int index) {
			index++;
			int ans = 0;
			while (index > 0) {
				ans += this.bits[index];
				index -= this.lowbit(index);
			}
			return ans;
		}

		public int valueAt(int index) {
			return this.nums[index];
//			return this.query(index) - this.query(index - 1);
		}

		public void update(int index, int value) {
			int num = this.valueAt(index);
			int diff = value - num;
			this.add(index, diff);
		}

	}

	BinaryIndexedTree bit;

	public NumArray(int[] nums) {
		bit = new BinaryIndexedTree(nums.length);
		bit.initArray(nums);
	}

	public void update(int index, int val) {
		bit.update(index, val);
	}

	public int sumRange(int left, int right) {
		return bit.query(right) - bit.query(left - 1);
	}
}